package arithmetic.leecode_arthmetic;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 * 描述：
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 实现算法：递归
 * 网站地址：<a href="https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 */
public class Solution70 {

    /**
     * 使用递归方式求解 有严重的效率问题
     * 时间复杂度O(n^2)
     * @param n:台阶数
     * @return：次数
     */
    public int climbStairsByRecursion(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        return climbStairsByRecursion(n - 1) + climbStairsByRecursion(n - 2);
    }


    Map<Integer, Integer> storeMap = new HashMap<>();

    /**
     * 递归求解-借助一个map存储中间值
     * 时间复杂度O(n)
     * @param n：台阶数
     * @return：次数
     */
    public int climbStairsByRecursion2(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (storeMap.get(n) != null) {
            return storeMap.get(n);
        } else {
            int count = climbStairsByRecursion(n - 1) + climbStairsByRecursion(n - 2);
            storeMap.put(n, count);
            return count;
        }
    }

    /**
     * 使用循环方式求解
     * 时间复杂度：O(n)
     * @param n：台阶数
     * @return：次数
     */
    public int climbStairsByFor(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int one = 1;
        int second = 2;
        int finalN = 0;
        for (int i = 3; i <= n; i++) {
            finalN = one + second;
            one = second;
            second = finalN;
        }
        return finalN;
    }

    public static void main(String[] args) {
        Solution70 solution70 = new Solution70();
        System.out.println(solution70.climbStairsByFor(5));
    }
}
